package com.chimm.main;

import java.util.Arrays;

/**
 * 快速排序
 * <p>
 * 1. 选择第一个数为p，小于p的数放在左边，大于p的数放在右边
 * 2. 递归j将p左边的数和右边的数按照第一步进行，直到不能递归。
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] a = {32, 43, 23, 13, 5}; //定义无序数组
        int start = 0; //开始索引
        int end = a.length - 1; //结束索引

        quickSort(a, start, end);
    }


    /**
     * 快速排序
     *
     * @param numbers 需要排序的数组
     * @param start   开启索引
     * @param end     结束索引
     */
    public static void quickSort(int[] numbers, int start, int end) {
        if (start < end) {
            int base = numbers[start]; //选定基准值
            int temp;

            int i = start;
            int j = end;

            do {
                //如果基数左边的值小于基数，则右移动i指针
                while ((numbers[i] < base) && (i < end)) {
                    i++;
                }
                //如果基数右边的值大于基数，则左移动j指针
                while ((numbers[j] > base) && (j > start)) {
                    j--;
                }

                //如果不属于上面的情况，则交换基数的位置
                if (i <= j) {
                    temp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = temp;
                    i++;
                    j--;
                }
                System.out.println(Arrays.toString(numbers));
            } while (i <= j);

            if (start < j) {
                quickSort(numbers,start,j);
            }
            if (end > i) {
                quickSort(numbers, i, end);
            }
        }
    }
}
